A Decade of Mazes

I've been making mazes for over a decade. It started with pen and paper, moved to algorithms, and eventually grew into generators for hexagonal grids, circular layouts, and various other geometries. At some point a question started nagging me: what makes one maze feel different from another maze with the same dimensions?

Two 20×20 mazes can have completely different characters. One feels open and flowing, the other cramped and fractal. The walls are different, sure, but the walls are just negative space. What actually differs is the topology: the structure of connections between cells. The shape of the graph, not the shape of the corridors.

From ASCII to Eigenvalues

The pipeline starts with a simple ASCII maze (# for walls, spaces for passages) parsed into a 4-connected passage graph where each open cell is a node and each adjacent pair shares an edge.

From there it's standard spectral graph theory. Build the adjacency matrix A in NetworkX, compute the degree matrix D, form the normalized Laplacian:

L_norm = D^(-1/2) (D - A) D^(-1/2)

The eigenvalues of L_norm encode the maze's global structure. The smallest is always 0 (connected graph). The second-smallest, the Fiedler value, measures how well-connected the maze is: high Fiedler means many alternative paths; low Fiedler means there's a bottleneck somewhere, a narrow passage the entire maze funnels through.

The eigenvectors are more interesting still. The 2nd and 3rd smallest eigenvectors of the Laplacian give a natural 2D embedding of the maze's topology: plot each cell at the coordinates given by these two eigenvectors and you get a picture of the maze's connectivity structure independent of its physical layout.

Spectral embedding of a maze graph showing spatial layout from eigenvectors
A maze's graph laid out by its second and third Laplacian eigenvectors. The spectral embedding reveals the maze's true topological structure.

Editing Eigenvalues

This works in reverse. Decompose a maze into its eigenbasis, modify the eigenvalues, reconstruct the adjacency matrix, and you change how the maze feels without touching individual walls.

I built an interactive tool with ipywidgets: a 5×5 grid with sliders controlling the eigenvalues. Push the Fiedler value up and the maze opens up (more paths, fewer dead ends). Push it down and bottlenecks emerge. Higher eigenvalues control the fine-grained texture: whether the maze has small loops or long winding corridors.

The reconstruction from modified eigenvalues back to an adjacency matrix isn't exact; you get a real-valued matrix that needs thresholding to produce binary connections. Different thresholds produce different interpretations of the "same" spectral modification, which is both a nuisance and a source of unexpected variety.

Tensor Factorization

A complementary approach: the adjacency matrix of a grid-based maze can be reshaped into a 4-dimensional tensor with indices (x₁, y₁, x₂, y₂), where each entry indicates whether cell (x₁, y₁) connects to cell (x₂, y₂).

Non-negative PARAFAC decomposition (via TensorLy) with rank 3 splits this into three structural components, roughly corresponding to horizontal flow, vertical flow, and local clustering. Less intuitive than the spectral approach, but it offers something eigenvalues don't: you can manipulate the spatial factors independently. Want a maze that flows freely horizontally but is tightly constrained vertically? Scale the corresponding factor.

The PARAFAC factors are mathematically clean but mapping them back to intuitive maze properties takes trial and error. Spectral methods win on interpretability; tensor methods win on manipulation flexibility.

Non-negative matrix factorization decomposition of maze structure
PARAFAC decomposition of the adjacency tensor, showing how the maze's connectivity breaks into rank-3 structural components.

What I Learned

Spectral methods reveal structure that visual inspection misses: two mazes can look similar on paper but have very different eigenvalue spectra. The spectrum captures connectivity, bottlenecks, and symmetry: things you'd need to actually solve the maze to discover otherwise.

The Fiedler value is worth tracking on its own. It's a single number that tells you whether a maze has a critical chokepoint or is robustly connected, and I now use it as a quality metric when generating mazes for other projects.

I spent most of my time on 5×5 and 7×7 grids. At that scale you can hold the entire structure in your head and verify the math is doing what you think it's doing. Scaling up was easy once the foundations were solid.

The direction I haven't explored yet is using spectral properties as constraints for generation: specify "Fiedler value around 0.3, third eigenvalue below 0.5" and have a generator produce a maze matching those specs. That would invert the workflow from analysis to design.